1. Field of Invention
The present invention relates generally to the field of relational database management systems. More specifically, the present invention is related to generating an IN-list to speed up predicate evaluation, whereby the total cost of evaluating the query (including the cost of the IN-list creation) is reduced.
2. Discussion of Related Art
Complex Business Intelligence (BI) queries are expensive as they often have large number of predicates, some of which can be very complex expressions. Therefore, efficient predicate evaluation is crucial in order to achieve fast BI query response times.
FIG. 1 illustrates an example of a prior art predicate evaluation scheme 100. In the prior art, predicate evaluation of a BI query consists of at least the following overheads: index scan—102, RID-list scan—104, table scan—106, expression calculation—108, decompression (in a compressed dataset)—110, etc. One problem associated with the approach outlined in FIG. 1 is that processing associated with each of the steps can render the process very time-consuming. Another problem associated with the approach of FIG. 1 is that time and resources are spent evaluating complex or expensive predicates for each tuple. Such evaluations do not take advantage of existing data structures that keep the distinct values of one column or multiple columns, such as dictionaries, indexes (i.e., database indexes, wherein a database index is a data structure representing a set of keys and pointers to the instances of that key inside a given column of a table), materialized views, etc. Usually, the number of distinct values of a column or a column group is much smaller than the number of tuples in a table. What is needed is a system, method and article of manufacture that takes advantage of such data structures.
The U.S. patent to Leslie et al. (U.S. Pat. No. 5,778,354) provides for a database management system with improved indexed accessing. Leslie et al. describe the generation of an IN-list based upon applying certain predicates over an index.
The U.S. patent to Koo et al. (U.S. Pat. No. 6,983,275) provides the optimization of database queries, wherein the approach of Koo et al. involves converting predicates with expressions into simpler predicates based on monotonicity of the values in a column.
Whatever the precise merits, features, and advantages of the above cited references, none of them overcomes the technical challenges that the present invention overcomes.